{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "# 软件技术基础引言\n",
    "\n",
    "## 基于软件的问题求解\n",
    "\n",
    "### 相关概念\n",
    "\n",
    "- 使用计算机是为了解决实际问题。牵涉到:   \n",
    "    - 能用计算机解决的问题的性质，特点   \n",
    "    - 用计算机解决问题的途径和方法\n",
    "\n",
    "- 解决一个实际问题，就要在计算机里建立该问题的求解模型:   \n",
    "    - 处理实际问题中的各种对象及其相互关系\n",
    "        >  把这方面信息映射到计算机可以处理的表示形式\n",
    "        用Python解决问题，就是映射到Python能处理的某种结构   \n",
    "    - 把实际问题的求解过程映射到一个计算过程，用程序实现该过程\n",
    "        >  例如，用Python语言写出解决问题的程序, 程序设计/软件开发就是要实现这两个映射\n",
    "        但，应该怎么做?\n",
    "\n",
    "- 为解决一个实际问题而开发程序的工作通常可分成下面四个阶段 未必能按顺序一次完成，经常需要反复。\n",
    "    1. 分析阶段:弄清需要求解的问题，给出尽可能严格的描述\n",
    "    2. 设计阶段:设计出与实际问题对应的求解方案，进而设计出有关实现的细节方案(信息到数据表示的映射，规划求解过程等) ---这部分工作与本课程关系最密切\n",
    "    3. 编码阶段:用某种计算机可以执行的形式，实现第 2 阶段的设计 与本课程有关，例如用 Python 编程\n",
    "    4. 测试和维护:确认得到的程序能解决问题，以及为满足某些实际目标 或需要而修改程序，扩充功能等\n",
    "\n",
    "### 问题求解实例\n",
    "下面通过一个例子展示这一过程\n",
    "\n",
    "- 假设现在需要为一个多叉路口设计一个信号灯管理系统\n",
    "- 具体路口的交通要求情况见下图，图中箭头表示单行方向\n",
    "\n",
    "    <img src=\"figures/crossmodel.png\" width = \"500\" alt=\"冲突图v\" align=center />\n",
    "\n",
    "&nbsp;\n",
    "\n",
    "- 不同行驶路线间可能出现冲突则存在安全问题。需要对行驶方向分组，使:\n",
    "    - 同属一组的各方向行驶的车辆，同时行驶可以保证安全\n",
    "    - 分组应该尽可能大一些，提高路口的效率\n",
    "\n",
    "- 所有可能通行方向(设计一种形式表示)\n",
    "    > A→B A→C A→D \n",
    "    B→A B→C B→D \n",
    "    D→A D→B D→C \n",
    "    E→A E→B E→C E→D\n",
    "\n",
    "- 本问题较复杂，要采用某种严格的描述方式，以便能把问题看得更清楚\n",
    "- 考虑如何基于这种抽象表示，进一步看清问题的实质\n",
    "- 行驶方向的分组，关键情况:\n",
    "    - 有些方向相互冲突，同时开放会相互阻碍，而且有撞车危险\n",
    "    - 为了安全，不应该为任意两个冲突的行驶方向同时开绿灯，因此它 们不能放入同一个分组\n",
    "    - 表示冲突的方式是在冲突方向之间划一条连线 通过认真分析，得到下面的冲突图\n",
    "  \n",
    "    <img src=\"figures/chongtu.png\" width = \"400\" alt=\"冲突图v\" align=center />\n",
    "\n",
    "&nbsp;\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 问题分析\n",
    "- 问题求解线索:把冲突图中的结点分组   \n",
    "    - 保证有边相连的结点不同组\n",
    "    - 同组行驶方向互不冲突，可同时通行\n",
    "- 问题:哪些结点可同组，共分为多少个组?\n",
    "    - 显然解:每个方向独立作为一个组\n",
    "    - 进一步目标:分组最少，同时通行方向多，提高路口利用率\n",
    "- 通过分析构造出问题的求解模型后，下步考虑求解算法的设计\n",
    "    - 算法设计研究求解问题的严格方法 \n",
    "    - 设计好的算法为编程实现提供了坚实的基础\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### 算法设计\n",
    "- 解决本问题(图着色问题)有许多方法\n",
    "- 方法1，通过穷举选出最优 \n",
    "    - 设法逐个枚举出所有可能的合法分组，在枚举过程中，记录遇到的最小分组个数和对应的分组情况\n",
    "  \n",
    "    - 这一过程一定能找到一个“最优”解(分组数最少的解)\n",
    "\n",
    "    - 缺点:可能组合数太多，逐个枚举需要指数时间(算法的效率低)\n",
    "        - 如果不同方向的集合比较大，求解时间可能长得无法忍受\n",
    "        - 交通路口的支路不多(超过4的情况不多见)，可以考虑这一算法\n",
    "\n",
    "&nbsp;\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 方法2. “贪心法” \n",
    "    - 这是一类典型的算法设计思路，基本想法是根据当时掌握的信息，尽可能地向得到解的方向推进 通常不能找到最优解，但能找到“可接受的”解\n",
    "\n",
    "    ```python\n",
    "    设法表示图 G # 记录图中的结点连接关系 \n",
    "    集合verts保存G中所有结点  # 建立初始状态\n",
    "    设置集合 groups = 空集 # 记录得到的分组，元素是集合\n",
    "    while 存在未着色结点 : # 用贪心法反复找新分组\n",
    "        选一种新颜色 \n",
    "        在未着色结点中给尽量多无互连边的点着色(构建一个分组) \n",
    "        记录新着色的结点组\n",
    "    # 算法结束时集合 groups 里记录着一种分组方式\n",
    "    ```\n",
    "\n",
    "    采用贪心法，按结点排列顺序试探(演示):\n",
    "\n",
    "    <img src=\"figures/jiedianpaixu.png\" width = \"400\" alt=\"节点排序\" align=center />\n",
    "\n",
    "    得到如下分组：\n",
    "    绿色:AB, AC, AD, BA, DC, ED \n",
    "    蓝色:BC, BD, EA\n",
    "    红色:DA, DB\n",
    "    白色:EB, EC"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&nbsp;\n",
    "\n",
    "- 考虑算法中缺失的细节:处理一种新颜色的着色\n",
    "    - 设 G 保存需着色图中结点相互连接的信息，\n",
    "    - verts 记录图中所有尚未着色结点，初始时 verts 是 G 中所有结点的集合\n",
    "    - newgroup 记录已确定可用当前新颜色着色的结点(一个集合)\n",
    "- 找出 verts 里中可用新颜色着色的结点集的程序段框架:\n",
    "    ```python\n",
    "    newgroup = set() \n",
    "    for v in verts :\n",
    "        if v 与 newgroup 中所有结点之间都没有边:\n",
    "            从 verts 中去掉 v\n",
    "            把 v 加入 newgroup\n",
    "    # 结束时 newgroup 里是可以用一种新颜色着色的结点 \n",
    "        # 用这段代替前面程序框架中主循环体里的一部分\n",
    "    ```\n",
    "\n",
    "&nbsp;\n",
    "- 细节处理:\n",
    "    - 颜色的表示? \n",
    "        - 可以用顺序的整数   \n",
    "    - 如何记录得到的分组?\n",
    "        - 可以把分组作为集合加入 groups 作为元素(集合中的集合)\n",
    "        - 具体颜色实际上不重要，可以记录(如用元组)或不记录\n",
    "\n",
    "&nbsp;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "- 贪心法着色的算法\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def coloring (G) : # 做图 G 的着色\n",
    "    color = 0\n",
    "    groups = set()\n",
    "    verts = vertexes(G) # 取得 G 的所有结点，依赖于图的表示 \n",
    "    while verts != set() :\n",
    "        newgroup = set() \n",
    "        for v in list(verts) :\n",
    "            if notAdjacentWithSet(v, newgroup, G): \n",
    "                newgroup.add(v)\n",
    "                verts.remove(v)\n",
    "        groups.add((color, newgroup))\n",
    "        color += 1\n",
    "    return groups"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "> 找出最小分组数其实不是一个简单工作。已发现的算法都是需要枚举所有组合。实际上，这个问题是**NP完全性**问题。\n",
    "\n",
    "&nbsp;\n",
    "\n",
    "-  如果希望提供最大行驶可能，问题就不是安全划分，而是基于安全划分 的分组最大化。可从划分扩充得到\n",
    "  \n",
    "-  第一种分组的扩充:\n",
    "    > 1:AB, AC, AD, BA, DC, ED \n",
    "    2:BC, BD, EA, **BA, DC, ED** \n",
    "    3:DA, DB, **BA, DC, ED, AD** \n",
    "    4:EB, EC, **BA, DC, ED, EA** \n",
    "    \n",
    "    后两组扩充时可在 AD 和 EA 任选\n",
    "    \n",
    "- 假设希望做一个程序，给它任一交叉路口信息，就能得到一种可行分组   上面分析已经给出了一种解决问题的方案(算法)\n",
    "- 解决问题的下一步是做出程序。怎么做?\n",
    "    \n",
    "&nbsp;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 问题和算法\n",
    "\n",
    "- 对一个给定问题，用某种严格方式描述一个求解过程，对该问题的每个实例，该过程都能给出解，这个描述就是解决该问题的一个算法，例子：\n",
    "    - 求任意实数 x 的平方根，是一个问题\n",
    "    - 下面描述不是算法: \n",
    "        - 取得那个大于等于0且使$y^2 = x$的$y$，因为它没给出一个可以按部就班遵照执行的求解过程\n",
    "    - 下面描述是一个算法(牛顿迭代法):\n",
    "        1. 任取一个非 0 的初始值 y(例如取 y = 1)\n",
    "        2. 如果 $y^2$ 与 x 足够接近，结束并把 y 当作 x 的平方根，求解完成\n",
    "        3. 取 $z = (y + x/y) / 2$\n",
    "        4. 令 y 取 z 作为新的值，回到步骤 2\n",
    "&nbsp;\n",
    "\n",
    "### 问题和实例\n",
    "\n",
    "- 一个“问题”是具有同样性质的实例的集合。例如\n",
    "    - 判断一个数是否素数，判 123 或 88793767 是否素数是其实例\n",
    "    - 求两个(两维)矩阵的乘积\n",
    "    - 将一个整系数多项式分解为不可约整系数多项式因子的乘积\n",
    "    - 将一个图像旋转 90 度\n",
    "    - 辨识数字相机取景图像里的人脸\n",
    "  \n",
    "- 可能用一个算法统一地求解一个问题的(所有)实例，为此需要\n",
    "    - 设计问题实例的表示\n",
    "    - 设计一个求解算法\n",
    "    - 使用算法就是把问题实例(的表示)送给它，得到相应的解\n",
    "\n",
    "- 有的问题(可以严格描述)没有算法(不可计算问题)；对一个问题，可能有不同的算法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题复杂性\n",
    "- 对一个具体的问题，可能存在许多解决它的算法\n",
    "    - 不同算法的复杂性可能不同\n",
    "    - 解决问题的算法的复杂性反过来刻画了问题的性质\n",
    "- 理论观点:解决一个问题的复杂性最低的算法，刻画了这个问题的 质 (问题的难度，问题的复杂性)\n",
    "    - 如果一个问题有复杂性较低的算法，它就是“较易”求解的问题\n",
    "    - 有关问题的复杂性的研究领域称为“计算复杂性”\n",
    "- 事实:有些问题，已经找到了复杂性很低的算法；有些问题，虽然已经做了很多努力，也没有找到复杂性较低的算法 \n",
    "\n",
    "    > 没找到并不说明没有，也可能有但还没发现(例:素数性判断)\n",
    "\n",
    "- 有些问题，已经证明了其最有效算法的复杂性 \n",
    "- 有些问题，已经找到最有效的算法(改进余地不大，常量因子)\n",
    "\n",
    "- 另一些情况:\n",
    "    - 有些问题，已经证明求解它的最高效算法也一定具有指数以上的复杂性。这种问题称为“难解问题”\n",
    "    - 只可能能有指数复杂性的算法，说明这些问题的规模较大的实例，(从实际的角度看)“不能”用计算机求解   \n",
    "\n",
    "- 注意上面“不能”的意义，不是数学意义(或理论意义)上的“不能”。\n",
    "    - 数学或理论的“不能”就是“不可计算”，可计算问题就是可求解的问题\n",
    "    - 实际意义上的“不能”是说，虽然这些问题理论上可计算，但对于它的具有一定规模的实例，没办法实际地得到计算结果\n",
    "\n",
    "例如：\n",
    "> RAS密匙，RSA算法基于一个十分简单的数论事实：将两个大质数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。是一种最常用的\b公匙加密算法，1977年提出。\n",
    "\n",
    "> RSA是目前最有影响力和最常用的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。\n",
    "\n",
    "> 到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。分解129位的质数\b需要1600台超级计算机计算8\b个月，而140位则要几百年。但在分布式计算和量子计算机理论日趋成熟的今天，RSA加密安全性受到了挑战和质疑。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 计算复杂性\n",
    "- 上面讨论区分了两种情况\n",
    "    - 理论上不可计算的问题(复杂/过于一般，不可能实现计算过程)   \n",
    "    - 实际意义上不能计算的问题(复杂性高，不存在高效算法)\n",
    "\n",
    "- 把计算复杂性纳入考虑，出现了另一个重要理论问题:\n",
    "    - 是否存在本质上比图灵机更快的计算模型?\n",
    "    - 即是问:是否存在“实际可计算能力”优于图灵机计算模型，它能有效解决某些在图灵机模型上不存在高效算法的问题?\n",
    "\n",
    "- 人们提出了一个“扩展的图灵论题”：在任何(非并行)计算模型上多项式时间可解的问题，必然在图灵机上多项式时间可解\n",
    "  \n",
    "- 与图灵论题类似，这一问题无法证明，只能否证。但有如下事实\n",
    "    - 已证明，目前已提出的各种重要计算模型，在多项式时间可解性方面与图灵机等价(也就是说，图灵机上需要指数以上时间求解的问题， 在这些模型上也不存在多项式算法)\n",
    "\n",
    "- 根据计算复杂性，可以对问题做一种分层(复杂性分层)\n",
    "    - 显然，属于低复杂性类的问题也属于更高的复杂性类\n",
    "- 这方面最重要成果是确定了一大批有重要实际意义的问题，它们\n",
    "    - 在具有无穷并行能力的计算机器上求解，时间复杂性为多项式的\n",
    "    - 在只有顺序处理能力或有限并行能力的计算机器上，其复杂性至今未确定(找到的算法都为指数时间，但尚 证明只有指数算法)\n",
    "\n",
    "- 由此引出的重要理论问题是:P =?= NP (P 与 NP 问题)，问题涉及到两个复杂性问题类\n",
    "    - 在顺序计算机器上多项式时间可解的问题类P\n",
    "    - 在具有无穷并行能力的计算机器上多项式时间可解的问题类NP\n",
    "\n",
    "> 美国克雷(Clay)数学研究所2000年5月宣布了七个悬赏一百万美元的 “世纪数学难题”: **P-NP问题、霍奇猜想、庞加莱猜想、黎曼假设、杨-米尔斯理论、纳维-斯托克斯方程、BSD猜想**\n",
    "\n",
    "- P-NP 问题被列为第一数学问题(传统的重大数学问题均列其后)，这一情况很有趣，说明了数学界对“计算”的重要性的评价\n",
    "    - 原本人们认为计算太简单，是最简单的数学\n",
    "    - P-NP 问题说明计算中存在极深刻的理论，其价值不亚于任何传统数学领域的理论。它有许多有价值的推论，人们已在用各种数学工具去研究它，解决它的过程必定给数学带来许多收获\n",
    "- 这一问题还有极其重大的实际意义\n",
    "    - 目前社会中几乎所有现代意义下的安全性，都依赖于 NP ≠ P。一旦有人证明了 NP = P，所有重要领域的许多系统(军事、金融、 通讯等)都需要重建。同时我们也看到了计算能力的新边界，社会 生产生活各方面的效率都可能大大提高\n",
    "    - 如果证明了 NP ≠ P，我们的生活环境不会有什么变化，但人类又进一步认识到自己能力的局限性\n",
    "- 从来没有过一个数学问题如此深刻地影响(威胁?)整个人类社会\n",
    "\n",
    "&nbsp;\n",
    "\n",
    "<!-- ### NP完全性问题\n",
    "\n",
    "- 深刻的数学理论问题常显示出美妙的结构。P 与 NP 问题是这方面的典范。其中最有趣的问题之一是 NP 完全性\n",
    "\n",
    "- NP 问题类里有一个子集称为 NP 完全性问题(类)，有如下结论\n",
    "    - 任意两个 NP 完全性问题可通过多项式时间复杂性的变换相互转换。 因此只需多项式时间就可以基于一个 NP 完全性问题的解得到另一个 NP 完全性问题的解:只需定义两个适当的多项式时间的翻译算法，就能解决另一NP完全性问题\n",
    "    - 任一 NP 问题都可通过多项式时间变换到某 NP 完全性问题\n",
    "\n",
    "- 推论:任一个 NP 问题都可以通过多项式时间变换归结到某个 NP 完全性问题(也就是说，变换到任意一个 NP 完全性问题)   重要结论:\n",
    "    - 要证明 NP ≠ P，只需证明一个 NP 问题没有多项式时间算法\n",
    "    - 要证明 NP = P，只需证明一个 NP 完全性问题有多项式时间算法\n",
    "\n",
    "\n",
    "### 几个NP完全性问题\n",
    "\n",
    "- 现在举几个典型的 NP 完全性问题\n",
    "    - 货郎担问题:\n",
    "        - 设有 n 个村庄，村庄之间均有路相连，每条路有一定长度\n",
    "        - 要求找一条最短的路径，它经过每个村庄一次，最后回到出发点\n",
    "\n",
    "    - 货物打包问题:\n",
    "        - 设有多种货物，每种有一定重量。货车一台有确定载重量\n",
    "        - 要求选出一组货品，货车可以承载且在所有可能组合中重量最大 \n",
    " \n",
    "    - 哈密尔顿圈问题:\n",
    "        - 在一个图中有一些点，有的点之间有连线\n",
    "        - 问图中是否存在一条环路，它经过每个点且只经过一次\n",
    " -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 算法（Algorithm）\n",
    "\n",
    "### 算法的描述\n",
    "- 算法是问题求解过程的精确描述，具有如下性质:\n",
    "  - 有穷性(描述的有穷性):由有限条“指令”/“语句”构成\n",
    "  - 可行性:指令(语句)含义简单明确，其过程可以完全机械地进行\n",
    "  - 确定性:作用于所求解问题的给定输入(要处理的问题实例的某种 描述)，将产生出唯一的确定的动作序列\n",
    "  - 终止性(行为的有穷性):产生的动作序列有穷，它或终止并给出问题的解;或终止并指出对给定的输入问题无解（也存在不要求终止的计算描述，或称为“过程 (pocedure)”）\n",
    "  - 输入/输出:有确定的输入和输出\n",
    "\n",
    "&nbsp;\n",
    "- 算法可以用不同的方式描述 \n",
    "    - 需要在易读易理解和严格性之间取得某种平衡\n",
    "- 用自然语言描述的计算过程(可能易读，但可能出现歧义) \n",
    "    - 如在自然语言描述中结合一些数学形式的描述(减少歧义)\n",
    "- 采用严格的形式化记法形式描述。例如\n",
    "    - 用图灵机模型描述，定义完成该计算的图灵机(可能极不易读)\n",
    "    - 用某种严格的形式化算法描述语言描述算法\n",
    "- 采用伪代码形式，结合严格描述和自然语言\n",
    "    - 用类似程序语言的方式描述算法过程，其中用一些数学符号和记法描述细节和操作(如前面平方根算法描述用了控制转移结构)\n",
    "    - 例如，用 Python 语言结构，结合自然语言的局部功能说明\n",
    "&nbsp;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 算法和程序\n",
    "- 一个算法，描述了一个问题的解决过程，通常主要供人看，供人思考和 理解相应的问题求解方法、技术和过程\n",
    "- 人可以按算法一步步工作，完成具体问题实例的求解 \n",
    "    例如，按前面算法，求出 2 的精确到 5 位小数的平方根\n",
    "- 计算问题通常很复杂，人工做不现实，只能处理很简单问题的规模很小的实例。利用自动化的计算机器完成复杂计算工作，就是要指挥计算机完成计算，解决有实际价值的问题。\n",
    "\n",
    "&nbsp;\n",
    "- 算法和程序密切相关\n",
    "    - 每一个程序的背后，都隐藏着一个或一些算法。正确实现的程序能解决相关算法所解决的问题，其(运行时的)动态性质反应了相关算法的特征(是相应算法的合理实现)\n",
    "    - 程序用某种计算机能处理的具体编程语言描述，通常会包含一些与具体语言有关的细节结构和描述方式方面的特征\n",
    "- 在抽象考虑一个计算过程，或考虑该计算过程的抽象性质时，人们常用 “算法”作为术语，指称相应计算过程的描述\n",
    "- 在考虑一个计算(在某种语言里)的具体实现和实现中的问题时，人们 常用“程序”这一术语讨论相关问题\n",
    "- 有时我们写一个程序，但讨论时却说“算法”。实际上是指该程序背后的与具体语言无关的计算过程\n",
    "\n",
    "&nbsp;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 算法的设计\n",
    "\n",
    "- 实际应用中的算法，表现形式千变万化\n",
    "    - 但是许多算法的设计思想有相似之处\n",
    "    - 可以对它们分类，进行学习和研究(后面例子和讨论)\n",
    "- 设计算法的一些核心的通用想法可以称为算法设计模式。常见:\n",
    "    - 贪心法\n",
    "    - 分治法\n",
    "    - 回溯法(搜索法)\n",
    "    - 动态规划法\n",
    "    - 分支限界法\n",
    "- 对于算法，没有**放之四海而皆灵**的设计理论或技术，只能借鉴 \n",
    "- 算法是智力活动的产物，一个好算法至少**等价于一个好定理和证明**。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 参考资料：\n",
    "> 真正统治世界的十大算法\n",
    "> 1. 归并排序，快速排序和堆排序\n",
    "> 2. 傅立叶变换与快速傅立叶变换\n",
    "> 3. Dijkstra 算法\n",
    "> 4. RSA算法\n",
    "> 5. 安全哈希算法\n",
    "> 6. 整数因式分解\n",
    "> 7. 链接分析\n",
    "> 8. 比例积分微分算法\n",
    "> 9. 数据压缩算法\n",
    "> 10. 随机数生成\n",
    "\n",
    "&nbsp;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 算法分析\n",
    "\n",
    "一些普遍的现象是，刚接触计算机科学的学生会将自己的程序和其他人的相比较。你可能还注意到，这些计算机程序看起来很相似，尤其是简单的程序。经常出现一个有趣的问题。当两个程序解决同样的问题，但看起来不同，哪一个更好呢？\n",
    "\n",
    "为了回答这个问题，我们需要记住，程序和程序代表的底层算法之间有一个重要的区别。正如我们在第 1 章中所说，一种算法是一个通用的，一步一步解决某种问题的指令列表。它是用于解决一种问题的任何实例的方法，给定特定输入，产生期望的结果。另一方面，程序是使用某种编程语言编码的算法。根据程序员和他们所使用的编程语言的不同，可能存在描述相同算法的许多不同的程序。\n",
    "\n",
    "要进一步探讨这种差异，请参考 _ActiveCode 1_ 中显示的函数。这个函数解决了一个我们熟悉的问题，计算前n个整数的和。该算法使用初始化值为 0 的累加器（`accumulator `）变量。然后迭代n个整数，将每个依次添加到累加器。\n",
    "\n",
    "\n",
    "###### ActiveCode 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sumOfN(n):\n",
    "    theSum = 0\n",
    "    for i in range(1,n+1):\n",
    "        theSum = theSum + i\n",
    "\n",
    "    return theSum\n",
    "\n",
    "print(sumOfN(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "现在看看 _ActiveCode 2_ 中的函数。乍一看，它可能很奇怪，但进一步的观察，你可以看到这个函数本质上和前一个函数在做同样的事情。不直观的原因在于编码习惯不好。我们没有使用良好的标识符（`identifier`）名称来提升可读性，我们在迭代步骤中使用了一个额外的赋值语句，这并不是真正必要的。\n",
    "\n",
    "###### ActiveCode 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def foo(tom):\n",
    "    fred = 0\n",
    "    for bill in range(1,tom+1):\n",
    "        barney = bill\n",
    "        fred = fred + barney\n",
    "\n",
    "    return fred\n",
    "\n",
    "print(foo(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "先前我们提出一个问题是哪个函数更好，答案取决于你的标准。如果你关注可读性，函数 *sumOfN* 肯定比 *foo* 好。事实上，你可能已经在介绍编程的课程中看到过很多例子，他们的目标之一就是帮助你编写易于阅读和理解的程序。然而，在本课程中，我们对算法本身的表示更感兴趣（当然我们希望你继续努力编写可读的，易于理解的代码）。\n",
    "\n",
    "算法分析是基于每种算法使用的计算资源量来比较算法。我们比较两个算法，说一个比另一个算法好的原因在于它在使用资源方面更有效率，或者仅仅使用的资源更少。从这个角度来看，上面两个函数看起来很相似。它们都使用基本相同的算法来解决求和问题。\n",
    "\n",
    "在这点上，重要的是要更多地考虑我们真正意义上的计算资源。有两种方法，一种是考虑算法解决问题所需的空间或者内存。解决方案所需的空间通常由问题本身决定。但是，有时候有的算法会有一些特殊的空间需求，这种情况下我们需要非常仔细地解释这些变动。\n",
    "\n",
    "作为空间需求的一种替代方法，我们可以基于算法执行所需的时间来分析和比较算法。这种测量方式有时被称为算法的“执行时间”或“运行时间”。我们可以通过基准分析（`benchmark analysis`）来测量函数 *SumOfN* 的执行时间。这意味着我们将记录程序计算出结果所需的实际时间。在 Python 中，我们可以通过记录相对于系统的开始时间和结束时间来对函数进行基准测试。在 *time* 模块中有一个 *time* 函数，它可以在任意被调用的地方返回系统时钟的当前时间（以秒为单位）。通过在开始和结束的时候分别调用两次 *time* 函数，然后计算差异，就可以得到一个函数执行花费的精确秒数（大多数情况下是这样）。\n",
    "\n",
    "######Listing 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "def sumOfN2(n):\n",
    "    start = time.time()\n",
    "\n",
    "    theSum = 0\n",
    "    for i in range(1,n+1):\n",
    "        theSum = theSum + i\n",
    "\n",
    "    end = time.time()\n",
    "\n",
    "    return theSum, end-start"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Listing 1 嵌入了时间函数，函数返回一个包含了执行结果和执行消耗时间的元组（`tuple`）。如果我们执行这个函数 5 次，每次计算前 10,000 个整数的和，将得到如下结果：\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(5):\n",
    "       print(\"Sum is %d required %10.7f seconds\" %sumOfN(10000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "我们发现时间是相当一致的，执行这段代码平均需要0.0019秒。如果我们运行计算前 100,000 个整数的和的函数呢？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(5):\n",
    "    print(\"Sum is %d required %10.7f seconds\"%sumOfN(100000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```python\n",
    "Sum is 5000050000 required  0.0199420 seconds\n",
    "Sum is 5000050000 required  0.0180972 seconds\n",
    "Sum is 5000050000 required  0.0194821 seconds\n",
    "Sum is 5000050000 required  0.0178988 seconds\n",
    "Sum is 5000050000 required  0.0188949 seconds\n",
    ">>>\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "再次的，尽管时间更长，但每次运行所需的时间也是非常一致的，平均大约多10倍。 对于 n 等于 1,000,000，我们得到：\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(5):\n",
    "    print(\"Sum is %d required %10.7f seconds\"%sumOfN(1000000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```python\n",
    "Sum is 500000500000 required  0.1948988 seconds\n",
    "Sum is 500000500000 required  0.1850290 seconds\n",
    "Sum is 500000500000 required  0.1809771 seconds\n",
    "Sum is 500000500000 required  0.1729250 seconds\n",
    "Sum is 500000500000 required  0.1646299 seconds\n",
    ">>>\n",
    "```\n",
    "在这种情况下，平均值也大约是前一次的10倍。现在考虑 *ActiveCode 3*，它显示了求解求和问题的不同方法。函数 *sumOfN3* 利用*封闭方程*而不是迭代来计算前n个整数的和。\n",
    "\n",
    "$$\\sum_{i=1}^n=\\frac{n(n+1)}{2}$$\n",
    "\n",
    "######ActiveCode 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sumOfN3(n):\n",
    "   return (n*(n+1))/2\n",
    "\n",
    "print(sumOfN3(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "如果我们对 *sumOfN3* 做同样的基准测试，使用 5 个不同的 n `(10,000, 100,000, 1,000,000, 10,000,000 和 100,000,000)`, 我们得到如下结果\n",
    "\n",
    "```python\n",
    "Sum is 50005000 required 0.00000095 seconds\n",
    "Sum is 5000050000 required 0.00000191 seconds\n",
    "Sum is 500000500000 required 0.00000095 seconds\n",
    "Sum is 50000005000000 required 0.00000095 seconds\n",
    "Sum is 5000000050000000 required 0.00000119 seconds\n",
    "```\n",
    "\n",
    "在这个输出中有两件事需要重点关注，首先上面记录的执行时间比之前任何例子都短，另外他们的执行时间和 n 无关，看起来 *sumOfN3* 几乎不受 n 的影响。\n",
    "\n",
    "但是这个基准测试能告诉我们什么？我们可以很直观地看到使用了迭代的解决方案需要做更多的工作，因为一些程序步骤被重复执行。这可能是它需要更长时间的原因。此外，迭代方案执行所需时间随着 *n* 递增。另外还有个问题，如果我们在不同计算机上或者使用不用的编程语言运行这个函数，我们也可能得到不同的结果。如果使用老旧的计算机，可能需要更长时间才能执行完 *sumOfN3*。\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "我们需要一个更好的方法来描述这些算法的执行时间。基准测试计算的是程序执行的实际时间。它并不真正地提供给我们一个有用的度量（`measurement`），因为它取决于特定的机器，程序，时间，编译器和编程语言。 相反，我们希望有一个独立于所使用的程序或计算机的度量。这个度量将有助于独立地判断算法，并且可以用于比较不同实现方法的算法的效率。\n",
    "\n",
    ">- 算法需要实际使用(转变为程序)，为此需要理解\n",
    "    - 需要考察算法的性质，比较算法的优劣，理解算法的适应范围   \n",
    "    - 算法分析:度量算法性质的工作\n",
    "    - 最常需要考虑的特性是算法的时间和空间开销(因为要实际使用)   \n",
    "    - 度量一个算法的开销，需要有合理统一的标准\n",
    ">- 处理问题的小实例和大实例，开销通常不同\n",
    "    - 开销通常都依赖于问题实例的规模\n",
    "    - 算法所用时间和空间通常会随着实例规模的增大而增长\n",
    ">- 即使规模相同，处理不同实例的代价也可能不同。对两个算法，\n",
    "    - 可以考虑其解决同样规模实例的平均代价\n",
    "    - 也可以考虑其解决同样规模实例的最大代价(最坏情况)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "&nbsp;\n",
    "### 计算代价的意义\n",
    "- 在考虑求解一个问题的具体算法时，需要考虑用它解决问题的代价   \n",
    "    - 求解过程中需要多少存储空间(需关心存储占用的高位限)   \n",
    "    - 完成问题实例的求解需要多少时间\n",
    "- 对算法性质的认识非常重要\n",
    "    - 比较解决同一问题的不同算法。一般说，使用资源少的算法更可取\n",
    "    - 估计一件计算工作完成的可能性和时间：\n",
    "        - 具体机器的存储量是否够用\n",
    "        - 在实际所要求的时间内能否完成\n",
    "- 例如:\n",
    "    - 做天气预报的程序，必须今天下午完成明天的预报计算\n",
    "    - 数字相机的人脸识别程序，必须在几分之一秒完成工作。用户不会接受更慢的算法。对这类问题，如果找不到效率够高的好算法，可以考虑不那么准确但更快速的算法\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "&nbsp;\n",
    "### 问题实例规模与算法代价\n",
    "\n",
    "- 问题实例通常可以基于某种规模度量，反映实例大小，决定计算开销\n",
    "    - 被判断素数性的整数的大小(或者数的长度)\n",
    "    - 求乘积的两个矩阵的各个维的长度\n",
    "    - 多项式的次数(或者长度)\n",
    "    - 被旋转或被辨识的图像的大小(长和宽的像素数，或它们的乘积)\n",
    "- 显然，一般而言，求解规模大的实例要付出更高的代价\n",
    "    - 考虑具体求解算法的代价时，应该用问题实例的规模作为参数\n",
    "    - 也就是说，算法的代价是用它求解的问题实例规模的函数\n",
    "\n",
    "- 例:求斐波那契数列（Fibonacci sequence，又称黄金分割数列），$F_i$ 的一个算法，定义是\n",
    "    $F_0 = F_1 = 1$\n",
    "    $F_n = F_{n-1} + F_{n-2}$, 对于$n>1$\n",
    "\n",
    "   <img src=\"figures/fib.jpeg\" width = \"400\" alt=\"fibonacci数列的花\" align=center />\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "### 求斐波那契数算法\n",
    "\n",
    "- 直接根据数学定义写出的算法（递归算法）:\n",
    "  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib(n) :\n",
    "      if n < 2 :\n",
    "         return 1\n",
    "      else :\n",
    "         return fib(n-1) + fib(n-2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "把参数$n$看作实例规模，可知计算$F_n$的时间代价(操作次数)大致等于计算 $F_{n-1}$ 和 $F_{n-2}$ 的时间代价之和。\n",
    "\n",
    "这一代价大约等于斐波那契数$F_n$的值，而且已有结论\n",
    "$$\n",
    "\\lim_{n \\to \\infty} = \\left(\\frac{\\sqrt{5}+1}{2}\\right)^n\n",
    "$$\n",
    "括号里表达式 $\\approx 1.618$，所以计算 $F_n$ 的时间代价按 $n$ 的值指数增长。对较大的$n$，这一计算需要很长很长时间.\n",
    "\n",
    "- 求斐波那契数的另一个算法:\n",
    "    - 对$F_0$和$F_1$直接给出结果\n",
    "    - 否则从$F_{k-1}$ 和$F_{k-2}$ 计算$F_k$，直至$k$等于$n$时给出$F_n$.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib(n) :\n",
    "    f1 = f2 = 1\n",
    "    for k in range(1, n) :\n",
    "        f1, f2 = f2, f2 + f1\n",
    "    return f2\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "- 计算$F_n$的值，循环前工作做一次，循环做 $n-1$ 次。每次循环执行几 个简单动作，总工作量(基本操作执行次数)与$n$值成某种线性关系\n",
    "\n",
    "> 这两个算法案例说明，解决同一问题的不同算法，计算代价的差异可以很大， 甚至性质截然不同。这也说明了分析算法(程序)复杂性的意义。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### 算法的时间和空间的代价\n",
    "\n",
    "- 空间代价\n",
    "    - 被解决实例的规模(以某种单位计量)为$n$时，求解算法所需要的存储空间按某种单位为 $S(n)$，称该算法的空间代价为$S(n)$\n",
    "- 时间代价\n",
    "    - 被求解实例的规模为$n$时，求解算法所耗费的时间以某种单位计算为$T(n)$，称该算法的时间代价为$T(n)$\n",
    "- 与度量有关的三个概念(需要根据实际问题确定): \n",
    "    - 问题规模\n",
    "    - 空间单位\n",
    "    - 时间单位\n",
    "- 对一个具体程序(算法的实现)，可能给出代价的精确估计\n",
    "    - 可能准确统计执行中所做的各种基 操作(作为规模 $n$ 的函数)\n",
    "    - 如果程序在具体计算机上运行，而且已知各基本操作所需时间，就可能算出程序执行所需的时间(也是规模 $n$ 的函数)\n",
    "\n",
    "- 对抽象算法，通常无法做精确度量 只能退而求其次，设法估计算法复杂性的量级\n",
    "    - 例:求两个 n×n 矩阵乘积的常规乘法算法\n",
    "        - 主要运算:乘法(或加法)\n",
    "        - 空间单位:一个元素所占存储 s\n",
    "        - 时间单位:一次乘法所用时间 t\n",
    "        - 实例规模:矩阵一行(一列)的元素个数\n",
    "        - 时间复杂性: $f(n) \\approx n*n*n=n^3$(单位为 t)\n",
    "        - 空间复杂性:只考虑完成算法所需空间，包括结果的存储空间和计算 中临时使用的辅助空间，这里约为$n^2$ (结果矩阵所需空间)\n",
    "  \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### 算法的时间和空间复杂性\n",
    "\n",
    "- 考虑时空代价时，有些因素的准确值意义不大，\n",
    "    - 例如：时间或空间的基本单位\n",
    "    - 算法描述和实现的细节差异\n",
    "- 人们最关注的是算法代价的关键情况和趋势，排除各方面具体细节   \n",
    "    - 从这种看法出发，人们定义了算法 “复杂性”的概念\n",
    "    - 同样，可以考虑时间和空间复杂性\n",
    "- 在理论上考虑复杂性时，通常忽略常量因子\n",
    "    - 例如，代价为 $3n^2$ 和 $100n^2$ 的算法，看作复杂性相同的算法\n",
    "    - 如果算法改进只是减小常量因子，从理论上看其复杂性没变，但在 实际中可能有意义\n",
    "        > 例:3 天算出明天的天气预报，与半天算出明天的天气预报\n",
    "\n",
    "### 平均和最坏情况\n",
    "- 对同一问题的同样规模的实例，算法计算的代价也 必一样\n",
    "    > 例如:在任意一个整数序列(如 Python 的 list)里找出第一个小于 0的整数的位置，找不到时给出一个特殊值(例如 –1) \n",
    "    算法:顺序检查序列里的整数。将表大小$n$作为实例规模(很合理)，对规模为 $n$ 的实例，可能出现多种不同情况\n",
    "        \n",
    "    1. 如果表中第一个元素就小于 0，计算中只需比较 1 次\n",
    "    2. 如果表中没有这样的整数，需要比较 n 次后才能给出结论 \n",
    "    3. 其他情况下的比较次数在 1 和 n 之间\n",
    "  \n",
    "- 情况 1 是最好情况，意义不大(世界上没有那么多好事)。\n",
    "- 情况 2 是最坏情况，给出了保证:算法在该时间期限内一定能完成指定工作。这 称为“最坏情况时间复杂性”。\n",
    "- 还可以考虑 “平均情况时间复杂性”，这 种复杂性依赖于实例的分布，需要做假设，而且不易计算\n",
    "> **我们主要关心最坏情况，有时关心平均情况**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "## 大O符号记法\n",
    "\n",
    "当我们试图通过执行时间来表征算法的效率时，并且独立于任何特定程序或计算机，重要的是量化算法需要的操作或者步骤的数量。选择适当的基本计算单位是个复杂的问题，并且将取决于如何实现算法。对于先前的求和算法，一个比较好的基本计算单位是对执行语句进行计数。在 sumOfN 中，赋值语句的计数为 1  `(theSum = 0)` 加上 n 的值（我们执行 `theSum=theSum+i` 的次数）。我们通过函数 T 表示  `T(n)=1 + n`。参数 n 通常称为‘问题的规模’，我们称作 ‘T(n) 是解决问题大小为 n 所花费的时间，即 1+n 步长’。在上面的求和函数中，使用 n 来表示问题大小是有意义的。我们可以说，100,000 个整数和比 1000 个问题规模大。因此，所需时间也更长。我们的目标是表示出算法的执行时间是如何相对问题规模大小而改变的。\n",
    "\n",
    "计算机科学家更喜欢将这种分析技术进一步扩展。事实证明，操作步骤数量不如确定  $T(n)$ 最主要的部分来的重要。换句话说，当问题规模变大时，T(n) 函数某些部分的分量会超过其他部分。函数的数量级表示了随着 n 的值增加而增加最快的那些部分。数量级通常称为大O符号，写为 `O(f(n))`。它表示对计算中的实际步数的近似。函数 f(n) 提供了 T(n) 最主要部分的表示方法。\n",
    "\n",
    "- 定义:如果存在两个正常数 $c$ 和 $n_0$，当实例的规模 $n\\ge n_0$ 后，某算法的时间(或者空间)代价$T(n)\\le cf(n)$，则说该算法的时间代价(或者空间代价)为 $O(f(n)$)\n",
    "    - 这个定义就是说，当实例的规模 $n$ 充分大时，该算法所需时间(空 间)不大于 $f(n)$ 的某个常数倍\n",
    "    - 也说该算法的时间(或空间)代价的增长率为 $f(n)$\n",
    "\n",
    "在上述示例中，`T(n)=1+n`。当 n 变大时，常数 1 对于最终结果变得越来越不重要。如果我们找的是 T(n) 的近似值，我们可以删除 1， 运行时间是 O(n)。要注意，1 对于 T(n) 肯定是重要的。但是当 n 变大时，如果没有它，我们的近似也是准确的。\n",
    "\n",
    "另外一个示例，假设对于一些算法，确定的步数是 $T(n)=5n^2 +27n+1005$。当 n 很小时, 例如 1 或 2 ，常数 1005 似乎是函数的主要部分。然而，随着 $n$ 变大，$n^2$ 这项变得越来越重要。事实上，当 n 真的很大时，其他两项在它们确定最终结果中所起的作用变得不重要。当 n 变大时，为了近似 $T(n)$，我们可以忽略其他项，只关注 $5n^2$ 。系数 5 也变得不重要。我们说，$T(n)$ 具有的数量级为 $f(n)=n^2$。 或者 $O( n^2 )$ 。\n",
    "\n",
    "\n",
    "虽然我们没有在求和示例中看到这一点，但有时算法的性能取决于数据的确切值，而不是问题规模的大小。对于这种类型的算法，我们需要根据最佳情况，最坏情况或平均情况来表征它们的性能。最坏情况是指算法性能特别差的特定数据集。而相同的算法不同数据集可能具有非常好的性能。大多数情况下，算法执行效率处在两个极端之间（平均情况）。对于计算机科学家而言，重要的是了解这些区别，使它们不被某一个特定的情况误导。\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### 复杂性增长的阶\n",
    "\n",
    "当你学习算法时，一些常见的数量级函数将会反复出现。见 Table 1。为了确定这些函数中哪个是最主要的部分，我们需要看到当 n 变大的时候它们如何相互比较。\n",
    "\n",
    "*Table 1 Big O functions*\n",
    "\n",
    "| $f(n)$      |    Name     |\n",
    "| ----------- | :---------: |\n",
    "| 1           |  Constant   |\n",
    "| \\(log n\\)   | Logarithmic |\n",
    "| \\(n\\)       |   Linear    |\n",
    "| \\(n\\log n\\) | Log Linear  |\n",
    "| \\(n^2\\)     |  Quadratic  |\n",
    "| \\(n^3\\)     |    Cubic    |\n",
    "| \\(2^n\\)     | Exponential |\n",
    "\n",
    "\n",
    "\n",
    "Figure 1 表示了 Table 1 中的函数图。注意，当 n 很小时，函数彼此间不能很好的定义。很难判断哪个是主导的。随着 n 的增长，就有一个很明确的关系，很容易看出它们之间的大小关系。\n",
    "\n",
    "   <img src=\"figures/newplot.png\" width = \"600\" alt=\"复杂性增长\" align=center />\n",
    "\n",
    "*Figure 1*\n",
    "\n",
    "最后一个例子，假设我们有 Listing2 的代码段。虽然这个程序没有做任何事，但是对我们获取实际的代码和性能分析是有益的。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "a=5\n",
    "b=6\n",
    "c=10\n",
    "for i in range(n):\n",
    "   for j in range(n):\n",
    "      x = i * i\n",
    "      y = j * j\n",
    "      z = i * j\n",
    "for k in range(n):\n",
    "   w = a*k + 45\n",
    "   v = b*b\n",
    "d = 33\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "分配操作数分为四个项的总和。第一个项是常数 3, 表示片段开始的三个赋值语句。第二项是 $3n^2$, 因为由于嵌套迭代，有三个语句执行 n^2 次。第三项是 2n, 两个语句迭代 n 次。最后，第四项是常数 1，表示最终赋值语句。最后得出 $T(n)=3+3n^2+2n+1=3n^2 +2n+4$，通过查看指数，我们可以看到 $n^2$ 项是显性的，因此这个代码段是 $O(n^ 2 )$。当 n 增大时，所有其他项以及主项上的系数都可以忽略。\n",
    "\n",
    "<img src=\"figures/newplot2.png\" width = \"600\" alt=\"复杂性增长\" align=center />\n",
    "\n",
    "**Figure 2 算法复杂度计算时间图**\n",
    "\n",
    "Figure 2 展示了一些常用的 大O 函数，跟上面讨论的 T(n) 函数比较，一开始的时候，T(n) 大于三次函数，后来随着 n 的增长，三次函数超过了 T(n)。T(n) 随着二次函数继续增长。\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### 算法复杂性\n",
    "\n",
    "- 大 $O$ 记法表示一个算法的复杂性的上界\n",
    "    - 显然，一般性的上界没什么意义(可以任意大)\n",
    "    - 最希望得到算法复杂性的上确界(的量级)，即算法(遇到最难做 的实例时)的最坏情况能达到的上界。但常常不容易确定\n",
    "    - 如不能得到上确界，也希望得到算法的尽可能紧的上界\n",
    "    - 通常讨论中总用大 $O$ 记法表示这样的上界\n",
    "- 常量时间的复杂性用 $O(1)$ 表示，线性复杂性是 $O(n)$，等等\n",
    "- 算法分析研究推导算法复杂性的技术，其主要技术是构造和求解递归方 程。后面将简单介绍有关情况\n",
    "\n",
    "- 易见，算法的复杂性分级就是(数学分析里)无穷大的阶: \n",
    "    > 在规模n趋于无穷大的过程中，算法的开销增长的速度\n",
    "- 算法复杂性高，其代价随规模增大而增长的速度快。重要吗?\n",
    "\n",
    "- 例:假设解决某具体问题的基本操作每秒做10000次，实例规模是n=100，\n",
    "    - $O(n)$ 的算法，所需时间可忽略不计(1/100秒)\n",
    "    - $O(n^3)$ 的算法，所需时间是分钟的量级\n",
    "    - $O(2^n)$ 的算法，所需时间是 $4.0*10^{18}$ 年的量级。(迄今为之的宇宙寿命估计为 $10^{10}$ 年的量级)\n",
    "    \n",
    "- 算法的复杂性反过来决定了算法的可用性:\n",
    "    - 如果一算法的复杂性较低，就可能用它去解决很大的实例   \n",
    "    - 如果一算法的复杂性高，它只能用于很小的实例。可用性低\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "### 复杂性地计算（推导/估计）\n",
    "\n",
    "算法的时间复杂性计算规则\n",
    "\n",
    "1. 加法规则(顺序复合)\n",
    "    > 如果所考虑的算法(或其中片段)分为两个部分(或者多个部分)，其复杂性是这两部分(或多部分)的复杂性之和\n",
    "    $$\n",
    "    \\begin{aligned}\n",
    "    T(n) &= T1(n) + T2(n) \\\\\n",
    "    &= O(T1(n)) + O(T2(n)) \\\\\n",
    "    &= O(\\max(T1(n), T2(n)))\n",
    "    \\end{aligned}\n",
    "    $$\n",
    "    由于忽略常量因子，加法等价于求最大值 \n",
    "\n",
    "2. 乘法规则(循环)\n",
    "如果算法中循环执行 $T1(n)$ 次，每次循环用 $T2(n)$ 时间，则 \n",
    "$$\n",
    "\\begin{aligned}\n",
    "T(n) &= T1(n)\\times T2(n) \\\\ \n",
    "&=O(T1(n))\\times O(T2(n)) \\\\\n",
    "&= O(T1(n)\\times T2(n))\n",
    "\\end{aligned}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### 复杂性地计算实例\n",
    "\n",
    "- 例:矩阵乘法，求两个 $n\\times n$ 矩阵 $\\bf m_1$, $\\bf m_2$ 的乘积 $m$\n",
    "\n",
    "假设矩阵实现为两层的表，已准备好保存结果的 m\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(n): \n",
    "    for j in range(n):\n",
    "        x=0\n",
    "        for k in range(n) :\n",
    "            x = x + m1[i][k] * m2[k][j] \n",
    "        m[i][j] = x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "复杂性的计算，以矩阵的维数作为 $n$: \n",
    "$$\n",
    "\\begin{aligned}\n",
    "T(n) &= O(n)\\times O(n)\\times (O(1)+O(n))) \\\\\n",
    "&= O(n)\\times O(n)\\times O(n) \\\\\n",
    "&= O(n\\times n\\times n) \\\\\n",
    "&= O(n^3)\n",
    "\\end{aligned}\n",
    "$$\n",
    "这个算法需要用一个 $n\\times n$ 的结果矩阵，只使用了一个辅助变量(空间是常量)，算法的空间复杂性是 $O(n^2)$\n",
    "\n",
    "- 例:求 n 阶方阵的行列式的值   \n",
    "    - 高斯消元法(一种算法):\n",
    "        - 列消元需要做 $O(n^2)$ 次乘法和减法\n",
    "        - 整个算法的复杂性是 $O(n^3)$   \n",
    "    - 采用行列式求值的定义\n",
    "        求 $n$ 阶行列式的值需要构造和计算 $n$ 个 $n-1$ 阶行列式\n",
    "        $$\n",
    "        \\begin{aligned}\n",
    "        T(n) &= n \\times ((n-1)^2 + T(n-1)) \\\\\n",
    "        &> n\\times T(n-1) \\\\\n",
    "        &= n\\times(n-1)\\times T(n-2) \\\\\n",
    "        &= O(n!)\n",
    "        \\end{aligned}\n",
    "        $$\n",
    "    - $O(n!)$ 比 $O(2n)$ 复杂性高。\n",
    "    显然，这种算法没有太大实际意义，对很小的 $n$ 就等不到计算结果了"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### 递归算法的复杂性\n",
    "\n",
    "- 对比较规范的递归算法，有清晰的理论分析方法 \n",
    "    前面行列式求值的递归算法的情况更复杂一些\n",
    "\n",
    "- 设一个递归求解算法，将规模为 $n$ 的问题实例归结到 $a$ 个规模为 $n/b$ 的子问题，每次递归时还需要做 $O(nk)$ 的其他工作，那么\n",
    "$$T(n) = a T(n/b) +  O(n^k)$$\n",
    "\n",
    "    求解这一递归方程，可以得到如下面结果：\n",
    "    - 当$a>b^k$时，$T(n) = O(n^{\\log_b a})$\n",
    "    - 当$a=b^k$时，$T(n) = O(n^k\\log n)$\n",
    "    - 当$a<b^k$时，$T(n) = O(n^{k})$\n",
    "    注意:这里的 a、b 和 k 是常量，可以覆盖大部分典型情况\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "## 例：一个乱序字符串检查的例子\n",
    "\n",
    "显示不同量级的算法的一个很好的例子是字符串的乱序检查。乱序字符串是指一个字符串只是另一个字符串字母的重新排列。例如，'heart' 和 'earth' 就是乱序字符串。'python' 和 'typhon' 也是。为了简单起见，我们假设所讨论的两个字符串具有相等的长度，并且他们由 26 个小写字母集合组成。我们的目标是写一个布尔函数，它将两个字符串做参数并返回它们是不是乱序。\n",
    "\n",
    "### 解法1: 顺序检查\n",
    "\n",
    "我们对乱序问题的第一个解法是检查第一个字符串是不是出现在第二个字符串中。如果可以检验到每一个字符，那这两个字符串一定是乱序。可以通过用 None 替换字符来了解一个字符是否完成检查。但是，由于 Python 字符串是不可变的，所以第一步是将第二个字符串转换为列表。检查第一个字符串中的每个字符是否存在于第二个列表中，如果存在，替换成 None。见 ActiveCode1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def anagramSolution1(s1,s2):\n",
    "    alist = list(s2)\n",
    "\n",
    "    pos1 = 0\n",
    "    stillOK = True\n",
    "\n",
    "    while pos1 < len(s1) and stillOK:\n",
    "        pos2 = 0\n",
    "        found = False\n",
    "        while pos2 < len(alist) and not found:\n",
    "            if s1[pos1] == alist[pos2]:\n",
    "                found = True\n",
    "            else:\n",
    "                pos2 = pos2 + 1\n",
    "\n",
    "        if found:\n",
    "            alist[pos2] = None\n",
    "        else:\n",
    "            stillOK = False\n",
    "\n",
    "        pos1 = pos1 + 1\n",
    "\n",
    "    return stillOK\n",
    "\n",
    "print(anagramSolution1('abcd','dcba'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "为了分析这个算法，我们注意到 s1 的每个字符都会在 s2 中进行最多 n 个字符的迭代。s2 列表中的 n 个位置将被访问一次来匹配来自 s1 的字符。访问次数可以写成 1 到 n 整数的和，可以写成 \n",
    "\n",
    "$$\\sum_{i=1}^n=\\frac{n(n+1)}{2} = \\frac{1}{2}n^2 + \\frac{1}{2}n$$\n",
    "\n",
    " \n",
    "当 $n$ 变大，$n^2$ 这项占据主导，1/2 可以忽略。所以这个算法复杂度为 $O(n^2 )$。\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "### 解法2: 排序和比较\n",
    "\n",
    "另一个解决方案是利用这么一个事实：即使 s1,s2 不同，它们都是由完全相同的字符组成的。所以，我们按照字母顺序从 a 到 z 排列每个字符串，如果两个字符串相同，那这两个字符串就是乱序字符串。见 ActiveCode2。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def anagramSolution2(s1,s2):\n",
    "    alist1 = list(s1)\n",
    "    alist2 = list(s2)\n",
    "\n",
    "    alist1.sort()\n",
    "    alist2.sort()\n",
    "\n",
    "    pos = 0\n",
    "    matches = True\n",
    "\n",
    "    while pos < len(s1) and matches:\n",
    "        if alist1[pos]==alist2[pos]:\n",
    "            pos = pos + 1\n",
    "        else:\n",
    "            matches = False\n",
    "\n",
    "    return matches\n",
    "\n",
    "print(anagramSolution2('abcde','edcba'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "首先你可能认为这个算法是 $O(n)$，因为只有一个简单的迭代来比较排序后的 n 个字符。但是，调用 Python 排序不是没有成本。正如我们将在后面的章节中看到的，排序通常是 $O(n^2)$ 或 $O(nlogn)$。所以排序操作比迭代花费更多。最后该算法跟排序过程有同样的量级。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### 解法3: 穷举法\n",
    "\n",
    "解决这类问题的强力方法是穷举所有可能性。对于乱序检测，我们可以生成 s1 的所有乱序字符串列表，然后查看是不是有 s2。这种方法有一点困难。当 s1 生成所有可能的字符串时，第一个位置有 n 种可能，第二个位置有 n-1 种，第三个位置有 n-3 种，等等。总数为 $n∗(n−1)∗(n−2)∗...∗3∗2∗1n∗(n−1)∗(n−2)∗...∗3∗2∗1$， 即$n!$。\n",
    "虽然一些字符串可能是重复的，程序也不可能提前知道这样，所以他仍然会生成 $n!$ 个字符串。\n",
    "\n",
    "事实证明，$n!$ 比 $n^2$ 增长还快，事实上，如果 s1 有 20个字符长，则将有 $20! = 2,432,902,008,176,640,000$ 个字符串产生。如果我们每秒处理一种可能字符串，那么需要 77,146,816,596 年才能过完整个列表。所以这不是很好的解决方案。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "### 解法4: 计数和比较\n",
    "\n",
    "我们最终的解决方法是利用两个乱序字符串具有相同数目的 a, b, c 等字符的事实。我们首先计算的是每个字母出现的次数。由于有 26 个可能的字符，我们就用 一个长度为 26 的列表，每个可能的字符占一个位置。每次看到一个特定的字符，就增加该位置的计数器。最后如果两个列表的计数器一样，则字符串为乱序字符串。\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def anagramSolution4(s1,s2):\n",
    "    c1 = [0]*26\n",
    "    c2 = [0]*26\n",
    "\n",
    "    for i in range(len(s1)):\n",
    "        pos = ord(s1[i])-ord('a')\n",
    "        c1[pos] = c1[pos] + 1\n",
    "\n",
    "    for i in range(len(s2)):\n",
    "        pos = ord(s2[i])-ord('a')\n",
    "        c2[pos] = c2[pos] + 1\n",
    "\n",
    "    j = 0\n",
    "    stillOK = True\n",
    "    while j<26 and stillOK:\n",
    "        if c1[j]==c2[j]:\n",
    "            j = j + 1\n",
    "        else:\n",
    "            stillOK = False\n",
    "\n",
    "    return stillOK\n",
    "\n",
    "print(anagramSolution4('apple','pleap'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "同样，这个方案有多个迭代，但是和第一个解法不一样，它不是嵌套的。两个迭代都是 n, 第三个迭代，比较两个计数列表，需要 26 步，因为有 26 个字母。一共 T(n)=2n+26T(n)=2n+26，即 O(n)，我们找到了一个线性量级的算法解决这个问题。\n",
    "\n",
    "在结束这个例子之前，我们来讨论下空间花费，虽然最后一个方案在线性时间执行，但它需要额外的存储来保存两个字符计数列表。换句话说，该算法牺牲了空间以获得时间。\n",
    "\n",
    "很多情况下，你需要在空间和时间之间做出权衡。这种情况下，额外空间不重要，但是如果有数百万个字符，就需要关注下。作为一个计算机科学家，当给定一个特定的算法，将由你决定如何使用计算资源。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "##  Python 程序的代价分析 \n",
    "\n",
    "### Python 程序的计算复杂性问题\n",
    "\n",
    "- Python 程序是算法的实现，因此也可以考虑其复杂性问题   \n",
    "- 需特别注意:Python 的很多基本操作不是常量时间的\n",
    "    - 基本算术运算是常量时间操作\n",
    "    - 组合对象操作有些是常量时间的，有些不是。例如:\n",
    "        - 复制和切片操作，通常需要线性时间($O(n)$ 操作)\n",
    "        - 表和元组的元素访问和元素赋值，是常量时间的  \n",
    "- 处理组合对象时需要特别考虑操作的复杂性问题\n",
    "    - 创建对象，需要空间/时间(都是线性复杂性，与对象大小相关)\n",
    "    - 内置复合数据类型的一些操作的情况后面讨论\n",
    "    - 用 Python 语言，很容易写出一些貌似正确但实际上完全不能用的 程序(复杂性太高，而且毫无必要)\n",
    "    - 今后写程序要强调这点（每个程序都要试着做复杂性分析）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "- 实例1：\n",
    "    - 考虑一个简单例子:假设要把得到的一系列数据存入一个表，假设得到 一个数据是 O(1) 常量时间操作。可以写\n",
    "  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name '还有数据' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-1-5ddb08e3b8e5>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[0mdata\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;33m[\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m \u001b[1;32mwhile\u001b[0m \u001b[0m还有数据\u001b[0m \u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      3\u001b[0m     \u001b[0mx\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0m下一数据\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      4\u001b[0m     \u001b[0mdata\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0minsert\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mx\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;31m#把新数据加在表的最前面\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mNameError\u001b[0m: name '还有数据' is not defined"
     ]
    }
   ],
   "source": [
    "data = []\n",
    "while 还有数据 :\n",
    "    x = 下一数据\n",
    "    data.insert(0,x) #把新数据加在表的最前面"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "或者写\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = []\n",
    "while 还有数据:\n",
    "    x = 下一数据\n",
    "    data.insert(len(data), x) # 把新数据加在表的最后面"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 思考问题：上面两种写法效率怎样?\n",
    " \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 实际情况:前一写法 $O(n^2)$ 复杂性，后一个是 $O(n)$ 复杂性，与表长度有关。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "- 实例2\n",
    "\n",
    "完成同一工作的不同方式。请自己试验看其代价随 $n$ 增长的趋势。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test1(n):\n",
    "    lst = []\n",
    "    for i in range(n * 10000):\n",
    "        lst = lst + [i]\n",
    "\n",
    "def test2(n):\n",
    "    lst = []\n",
    "    for i in range(n * 10000):\n",
    "        lst.append(i)\n",
    "\n",
    "def test3(n):\n",
    "    lst = [i for i in range(n * 10000)]\n",
    "\n",
    "def test4(n):\n",
    "    lst = list(range(n * 10000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 程序实现和效率陷阱\n",
    "\n",
    "- 用 Python 等高级语言编程，存在一些“效率陷阱”\n",
    "    - “效率陷阱”使原有可能用计算机做的事情变得“不行了”(时间代价太大)，至少也浪费了计算机和人的大量时间\n",
    "    - 这种缺陷很可能葬送一个软件，至少损害其可用性(降低其价值)\n",
    "\n",
    "- 常见的陷阱\n",
    "    - 程序里以递归的方式构造出一些复杂的结构(如 list 等)，而后只使用其中的个别元素\n",
    "    - 局部看，是使常量时间操作变成了线性时间操作;从递归算法的全局看，经常使多项式时间算法变成指数时间算法\n",
    "- 这些例子说明了一个情况:在 Python 这样的系统里有许多高级数据机制可用，但要有效使用，有必要了解数据结构的一些深入情况\n",
    "\n",
    "- 有关计算理论讨论至此暂告结束，网上可以找到许多参考材料"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "0ba00dd77806596ecbc07d55b4ddf41b2ae8cecbf91d9534027e74a33368b668"
  },
  "kernelspec": {
   "display_name": "Python 3.8.3 64-bit ('base': conda)",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
